ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpa/bishops/bishops_con_tabla.py

   1 casillas_por_diag_por_m = lambda m:\
   2                    (lambda k:k+1 if k < m else 2*m-k-1)
   3
   4 def alfiles(n,k):
   5     filas_negras = range(0,2*n-1,2) #son filas si giramos el tablero 45 grados
   6     filas_blancas = range(1,2*n-1,2)
   7     casillas_por_diag = casillas_por_diag_por_m(n)
   8     filas_negras.sort(cmp=lambda x,y: -1 if casillas_por_diag(x) < casillas_por_diag(y) else \
   9                       1 if casillas_por_diag(x) > casillas_por_diag(y) else 0)
  10     filas_blancas.sort(cmp=lambda x,y: -1 if casillas_por_diag(x) < casillas_por_diag(y) else \
  11                       1 if casillas_por_diag(x) > casillas_por_diag(y) else 0)
  12     # Memorizacion de resultados
  13     mem_negras=[[None for t in xrange(k+1)] for y in xrange(n+1)]
  14     mem_blancas=[[None for t in xrange(k+1)] for y in xrange(n+1)]
  15
  16     #inicializamos las tables
  17     for i in xrange(n+1):
  18         mem_blancas[i][0]=1
  19         mem_negras[i][0]=1
  20
  21     for j in xrange(1,k+1):
  22         mem_blancas[0][j]=0
  23         mem_negras[0][j]=0
  24
  25     acum = 0
  26
  27     if n%2==1:
  28         for t in xrange(k+1):
  29             acum += contar(n,t,filas_negras,mem_negras,casillas_por_diag)*contar(n-1,k-t,filas_blancas,mem_blancas,casillas_por_diag)
  30     else:
  31         for t in xrange(k+1):
  32             acum += contar(n,t,filas_negras,mem_negras,casillas_por_diag)*contar(n,k-t,filas_negras,mem_negras,casillas_por_diag)
  33     print acum
  34
  35 def contar(i,j,fs,mem,map):
  36     if mem[i][j] == None:
  37         aux = contar(i-1,j-1,fs,mem,map)
  38         aux2 =map(fs[i-1])-(j-1)
  39         mem[i][j] = aux*aux2
  40         mem[i][j] += contar(i-1,j,fs,mem,map)
  41     return mem[i][j]
  42
  43
  44 alfiles(8,7)
  45 alfiles(4,6)
  46 alfiles(6,7)
  47 alfiles(5,10)
  48 alfiles(5,8)
  49 alfiles(5,2)
  50 alfiles(500,300)
  51